package com.Questions.DP;


/**
 * 打家劫舍2
 */
public class leetcode213 {
    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        } else if (length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
    }


    public  int robRange(int[] nums,int start,int end){
        int[] dp=new int[nums.length-1];
        dp[0]=nums[start];
        dp[1]=Math.max(nums[start+1],nums[start]);
        for(int i=2;start+i<=end;++i){
            dp[i]=Math.max(dp[i-2]+nums[start+i],dp[i-1]);
        }
        return dp[nums.length-2];
    }
    //    public int robRange(int[] nums, int start, int end) {
//        int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
//        for (int i = start + 2; i <= end; i++) {
//            int temp = second;
//            second = Math.max(first + nums[i], second);
//            first = temp;
//        }
//        return second;
//    }
}
// 对于围成一圈的房屋 需要考虑的是 对于第一个房间 偷和不偷两种可能
// 如果偷 那么 动态规划的范围自然要去掉最后一个房屋 0 - length-2
// 如果不偷 那么动态规划的范围要去掉第一个房屋  1 - length-1

// 每一个空间的动态优化 可以使用滚动数组进行 空间的优化
// 说实话 空间上的维度优化是不那么重要的 尽量采用传统的动态规划数组
